package com.humngyang.com.hmy.study.shuzu;


/**
 * Description: 手写list的数据结构
 * Author: humingyang
 * Date: 2020/1/6 15:02
 */
public class MyArrayList {
    //空数组
    private long[] arr;
    //表示有效的数据长度
    private int ele;
    //默认的构造方法，默认长度为50
    public MyArrayList() {
        arr = new long[50];
    }
    //重载的构造方法,指定长度的数组长度
    public MyArrayList(int maxSize) {
        arr = new long[maxSize];
    }
    //添加数据 无序的
    public void myinsert(long value) {
        arr[ele] = value;//ele默认为0添加一次，索引值自增1
        ele++;
    }
    //添加有序的数组
    public void myinsertorder(long value) {
        int i;
        //目的是为了找到数组中大于当前的数据的索引
        for (i = 0; i <= ele - 1; i++) {
            if (arr[i] > value) {
                break;
            }
        }
        //找到对应大于数据的索引之后，将后面的值往后移一位
        for (int j = ele; j > i; j--) {
            arr[j] = arr[j - 1];
        }
        //必须等后面的数据全部移位之后才能进行添加值。
        arr[i] = value;
        //然后将数组的长度加一。因为长度移后了一位
        ele = ele + 1;
    }

    //显示数组的元素
    public void mydisplay() {
        System.out.print("[");
        for (int i = 0; i <= ele - 1; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.print("]");
    }

    //查找数据，根据value查找数据
    public int mysearchvalue(long value) {
        for (int i = 0; i <= ele; i++) {
            if (arr[i] == value) {
                return i;
            }
        }
        return -1;
    }
    //查找数据，根据index查找数据
    public long mysearchindex(int index) {

        if (index < 0 || index > ele) {
            throw new ArrayIndexOutOfBoundsException();
        }

        if (index <= ele) {
            return arr[index];
        }
        return -1;
    }

    //根据索引删除数据

    public void mydeleteindex(int index) {
        if (index > ele || index < 0) {
            throw new ArrayIndexOutOfBoundsException();
        }
        for (int i = 0; i <= ele; i++) {
            if (i == index && index <= i) {
                arr[index] = arr[index + 1];
                index++;
            }
        }
        ele = ele - 1;
    }
    //根据值删除数据

    public void mydeletevalue(long value) {
        int i;
        int index;
        for (i = 0; i <= ele; i++) {
            if (arr[i] == value) {
                index = i;
                //找到对应的value中的元素，然后调用索引删除的方法，删除元素
                this.mydeleteindex(index);
            }

        }

    }

    public void myupdate(int index, long value) {
        if (index > ele || index < 0) {
            throw new ArrayIndexOutOfBoundsException();
        }
        arr[index] = value;
    }

    //二分查找法查找value，提升查询的性能
    public int mybinarysearch(long value) {
        int mid = 0;
        int low = 0;
        int high = ele;
        while (true) {
            mid = (low + high) / 2;
            if (arr[mid] == value) {
                return mid;
            } else if (low > high) {
                return -1;
            } else {
                //如果中间值大于要查找的值，那么应该差左边的值
                if (arr[mid] > value) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
        }

    }


}
